package cn.zifangsky.hashtable.questions;

import cn.zifangsky.hashtable.Map;
import cn.zifangsky.hashtable.SeparateChainHashTable;
import org.junit.Test;

/**
 * RandomPool结构实现
 *
 * <p>设计一种结构，在该结构中有如下三个功能。</p>
 * <ol>
 *     <li>insert（key）：将某个key加入到该结构，做到不重复加入。</li>
 *     <li>delete（key）：将原本在结构中的某个key移除。</li>
 *     <li>getRandom（）：等概率随机返回结构中的任何一个key。</li>
 * </ol>
 *
 * @author zifangsky
 * @date 2020/7/3
 * @since 1.0.0
 */
public class Problem_001_RandomPool {

    @Test
    public void testMethod1() {
        RandomPool<String> pool = new RandomPool<>();

        //首先插入4个KEY
        pool.insert("A");
        pool.insert("B");
        pool.insert("C");
        pool.insert("D");
        System.out.println(String.format("随机获取2个KEY：【%s, %s】", pool.getRandom(), pool.getRandom()));

        //删除其中2个KEY
        pool.delete("B");
        pool.delete("D");
        System.out.println(String.format("再次随机获取2个KEY：【%s, %s】", pool.getRandom(), pool.getRandom()));
    }


    public static class RandomPool<K> {
        /**
         * KEY到Index的映射
         */
        private Map<K, Integer> keyIndexMap;

        /**
         * Index到KEY的映射
         */
        private Map<Integer, K> indexKeyMap;

        /**
         * 当前Pool中的数量
         */
        private int size;

        public RandomPool() {
            this.keyIndexMap = new SeparateChainHashTable<>();
            this.indexKeyMap = new SeparateChainHashTable<>();
            this.size = 0;
        }

        /**
         * 插入数据
         * @param key KEY
         */
        public void insert(K key){
            if(key != null && !this.keyIndexMap.containsKey(key)){
                this.keyIndexMap.put(key, this.size);
                this.indexKeyMap.put(this.size, key);
                this.size = this.size + 1;
            }
        }

        /**
         * 删除数据
         * @param key KEY
         */
        public void delete(K key){
            if(key != null && this.keyIndexMap.containsKey(key)){
                //1. 找到这个KEY对应的Index
                Integer deletedIndex = this.keyIndexMap.get(key);

                //2. 查询最后一个Index对应的KEY
                Integer lastIndex = this.size - 1;
                this.size = this.size - 1;
                K lastKey = this.indexKeyMap.get(lastIndex);

                //3. 将lastKey移动到待删除数据所在位置
                this.keyIndexMap.put(lastKey, deletedIndex);
                this.indexKeyMap.put(deletedIndex, lastKey);

                //4. 删除指定KEY
                this.keyIndexMap.remove(key);
                this.indexKeyMap.remove(lastIndex);
            }
        }

        /**
         * 随机返回一个KEY
         */
        public K getRandom(){
            if(this.size == 0){
                return null;
            }


            int rndIndex = (int) (Math.random() * this.size);
            return this.indexKeyMap.get(rndIndex);
        }
    }

}
